package com.lft.tree11.trie;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;
import java.util.stream.Collectors;

/**
 * 字典树/前缀树/Trie
 */
public class TrieDemo {
	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.add("goods");
		trie.add("good");
		trie.add("google");
		trie.add("gmail");
		trie.add("grade");
		trie.add("gender");
		
		System.out.println("删除之前：");
		System.out.println("是否包含good：" + trie.contains("good"));
		System.out.println("是否包含go前缀：" + trie.prefixContains("go"));
		System.out.println("找到 go 开头的单词：" + trie.commonPrefixSearch("go"));
		System.out.println("是否匹配 .ood：" + trie.match(".ood"));
		
		
		System.out.println();
		trie.delete("good");
		System.out.println("删除之后：");
		
		System.out.println("是否包含good：" + trie.contains("good"));
		System.out.println("是否包含go前缀：" + trie.prefixContains("go"));
		System.out.println("找到 go 开头的单词：" + trie.commonPrefixSearch("go"));
		System.out.println("是否匹配 .ood：" + trie.match(".ood"));
	}
}

class Trie {
	/**
	 * 根节点
	 */
	Node root;
	
	public Trie() {
		this.root = new Node();
	}
	
	/**
	 * 添加单词
	 * @param word
	 */
	public void add(String word) {
		Node cur = root;
		// 将字符串转换为 char 型数组
		char[] chars = word.toCharArray();
		for (char c : chars) {
			Map<Character, Node> children = cur.children;
			// 向 children 中 put 新值，如果key对应的值没有，就添加，否则返回原有的值。
			Node node = children.putIfAbsent(c, new Node());
			// 指针后移，继续添加后续字母。
			cur = children.get(c);
		}
		// 遍历完成之后
		cur.isWord = true;
	}
	
	/**
	 * 是否包含单词
	 */
	public boolean contains(String word) {
		return contains(word, true);
	}
	
	/**
	 * 是否包含前缀
	 */
	public boolean prefixContains(String prefix) {
		return contains(prefix, false);
	}
	
	/**
	 * 判断是否包含，前缀，单词
	 * @param prefix 前缀
	 * @param isWord 是否是按单词查找。
	 * @return boolean
	 */
	private boolean contains(String prefix, boolean isWord) {
		Node cur = root;
		// 将字符串转换成 char 型数组。
		char[] chars = prefix.toCharArray();
		// 遍历
		for (char c : chars) {
			// 从当前节点的子节点中获取 字母 c
			Node node = cur.children.get(c);
			// 如果获取到的为空。
			if (node == null) {
				// 直接返回 false
				return false;
			}
			// 指针后移。
			cur = node;
		}
		// 遍历完成判断是否需要按单词查找。
		if (isWord) {
			// 是返回当前节点是否是单词。
			return cur.isWord;
		} else {
			// 否则直接返回匹配包含。
			return true;
		}
	}
	
	/**
	 * 是否匹配单词，支持.匹配任意字符
	 */
	public boolean match(String word) {
		return match(root, word, 0);
	}
	
	/**
	 * 是否匹配单词，支持.匹配任意字符
	 * @param root  原始节点
	 * @param word  要匹配的单词
	 * @param index 从哪个索引开始匹配
	 * @return 能匹配返回 true,否则返回 false
	 */
	private boolean match(Node rootNode, String word, int index) {
		// 如果要查找的索引 等于 单词的长度。
		if (index == word.length()) {
			// 直接返回 当前节点是否是一个单词。
			return rootNode.isWord;
		}
		// 获得单词中 index 下的字母
		char c = word.charAt(index);
		// 如果字母不是 '.'
		if (c != '.') {
			// 获得当前节点的子节点。
			Node node = rootNode.children.get(c);
			return node != null && match(node, word, index + 1);
		} else {
			// 递归加回溯实现
			for (Map.Entry<Character, Node> entry : root.children.entrySet()) {
				if (match(entry.getValue(), word, index + 1)) {
					return true;
				}
			}
			return false;
		}
	}
	
	/**
	 * 查询所有以 prefix 为前缀的单词列表
	 */
	public List<String> commonPrefixSearch(String prefix) {
		Node cur = root;
		List<String> res = new ArrayList<>();
		// 将要搜索的前缀字符串转换为一个 char 型数组。
		char[] chars = prefix.toCharArray();
		// 遍历 前缀数组。
		for (char c : chars) {
			Node node = cur.children.get(c);
			// 没有了子节点
			if (node == null) {
				return res;
			}
			// 指针后移
			cur = node;
		}
		// 调用方法进行递归查询
		commonPrefixSearch(res, new ArrayList<Character>(), cur);
		return res.stream().map(x -> prefix + x).collect(Collectors.toList());
	}
	
	/**
	 * 从节点里查找字母表
	 * @param res  前缀搜索结果集
	 * @param list 字母表集
	 * @param node 需要搜索的根结点
	 */
	private void commonPrefixSearch(List<String> res, List<Character> list, Node node) {
		// 如果当前节点是一个单词
		if (node.isWord) {
			// 以字母表的大小创建一个新的 char 型数组
			char[] chars = new char[list.size()];
			for (int i = 0; i < list.size(); i++) {
				// 遍历单词表，将每个字母添加到数组中。
				chars[i] = list.get(i);
			}
			// 再将数组转成字符串，添加到搜索结果集中。
			res.add(new String(chars));
		}
		// 递归加回溯实现
		// 遍历根节点的每一个子节点
		for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
			// 将子节点的中的字母添加到 字母表中。
			list.add(entry.getKey());
			// 递归查找子节点。
			commonPrefixSearch(res, list, entry.getValue());
			// 从单词表中最后一个开始删除。
			list.remove(list.size() - 1);
		}
	}
	
	/**
	 * 删除单词
	 * @param word 要删除的单词
	 */
	public void delete(String word) {
		
		// 删除前查找是否存在这个单词，存在才能删除
		if (!contains(word)) {
			//不存在该单词，直接返回
			return;
		}
		Stack<Node> preNodes = new Stack<>();
		Node cur = root;
		for (int i = 0; i < word.length(); i++) {
			char c = word.charAt(i);
			//添加前驱节点
			preNodes.push(cur);
			cur = cur.children.get(c);
		}
		//到了单词末尾，节点是叶子节点
		if (cur.children.size() == 0) {
			for (int i = word.length() - 1; i >= 0; i--) {
				char c = word.charAt(i);
				//获得前驱节点
				Node pre = preNodes.pop();
				
				//判断是否为其他单词的结尾，是则停止删除节点
				//判断待删除节点是否还有其他孩子，有则停止删除节点
				if ((i != word.length() - 1 && pre.children.get(c).isWord) || pre.children.get(c).children.size() != 0) {
					break;
				}
				pre.children.remove(c);//删除节点
			}
		} else {
			cur.isWord = false;//情况2
		}
	}
}

/**
 * 节点的设计——第二版本
 * 舍去了 val，将指向下一节点的引用放在 map 里。此时暂时只考虑英文字符不考虑其他语言（中文等等）。
 */
class Node {
	/**
	 * 表示当前节点是否是一个单词
	 */
	boolean isWord;
	/**
	 * 节点的值，子节点
	 */
	Map<Character, Node> children;
	
	public Node() {
		this(false);
	}
	
	public Node(boolean isWord) {
		this.isWord = isWord;
		this.children = new TreeMap<>();
	}
}

// /**
//  * 节点的设计——第一版本
//  * 问题所在：
//  * 多余的 val，实际上指向该节点的引用中就包含了该节点的值是多少 ，所以 val 是多余的；
//  * 使用数组不合理，实际需求中不可能只有 26 个字母，也许有大小写，也许有其他符号，所以需要使用其他数据结构。
//  */
// class Node {
// 	boolean isWord;
// 	char val;
// 	char[] next = new char[26];
// }

